import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-08-06
 * Time: 22:36
 */

public class Solution {
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
        List<Integer> list = new ArrayList<>();
        dfs(arr, 0, k, n, list);
        return result;
    }

    private void dfs(int[] arr, int index, int k, int n, List<Integer> list) {
        // 满足条件
        if (k == 0 && n == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        // 越界, 或者已经不符合条件了
        if (index == arr.length || k <= 0 || n <= 0) {
            return;
        }
        // 正常情况
        // 不选这个数
        dfs(arr, index+1, k, n, list);
        // 选这个数
        list.add(arr[index]);
        dfs(arr, index+1, k-1, n-arr[index], list);
        list.remove(list.size()-1);

    }
}
